This invention relates to the design of electronic devices, such as integrated circuit chips and, more particularly, to the routing of nets in such chips to minimize the interconnection cost and to maximize the speed of operation.
From the prior art a number of approaches for designing very large scale integrated (VLSI) circuit chips is known especially as far as the routing of nets between the internal components of a chip are concerned. Channel routing is used extensively in the layout of integrated circuits and printed circuit boards. It is flexible enough to allow its use in various design styles such as gate-arrays, standard cells, and macro cells.
A channel router is designed to route nets that interconnect nodes on two opposite sides of a region called the channel. Criteria for a good channel router are that it routes the interconnections in a minimum area, the added length of the net wiring being also at a minimum. Examples for prior art channel routers are described for example in IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN, VOL. CAD-4, NO. 3, JULY 1985, pages 208-219, by James Reed et al and in xe2x80x9cCHAMELEON: A NEW MULTI-LAYER CHANNEL ROUTERxe2x80x9d, Douglas Braunt et al. IEEE, 1986, conference proceedings of the 23rd design automation conference.
In order to increase the overall quality of the routing attempts have been made to include information about the so called xe2x80x9cfeed-throughsxe2x80x9d in the process of channel routing. Such approaches are known from xe2x80x9cFEED THROUGH RIVER ROUTINGxe2x80x9d, A. Joseph et al, INTEGRATION, the VLSI Journal 8, pages 41-50, El Revier Science Publishers B.V., 1989 and xe2x80x9cMULTI CHANNEL OPTIMIZATION IN GATE-ARRAY LSI LAYOUTxe2x80x9d, K. Aoshima and E. S. Kuh, IEEE, 1983.
Since there is a constant need to further increase the wiring density in VLSI technology it is an underlying problem of the invention to devise an improved method for routing of nets for the design of electronic devices.
The underlying problem of the invention is solved basically by applying the features laid down in the independent claims. Preferred embodiments of the invention are given in the dependent claims.
The invention is advantageous in that it allows to design a VLSI layout requiring a minimum of silicon floor space which has a positive effect on chip yield and price. These extreme layout densities can be obtained by a fully automated solution which only requires moderate computing resources in terms of computer memory and run time.
The invention allows to generate separate sub graphs which contain the nodes to be connected both for the so called xe2x80x9ccluster areasxe2x80x9d and the xe2x80x9cchannel areasxe2x80x9d. These sub graphs are derived from input data which comprise the nodes of each net to be routed as well as the assignment of the nodes to clusters. Additional logical nodes which are defined by means of a minimal Steiner tree are inserted into the input data whereby the subgraphs are found. When the clusters are aligned horizontally it is advantageous to use rectilinear Steiner trees for defining such additional logical nodes.
Each cluster has one subgraph for each net to be wired. Analogously each channel has a dedicated subgraph for each net. As the subgraphs are descriptive of the interconnections to be established any method, including hand crafted design, can be used to actually route the subgraphsxe2x80x94or with other wordsxe2x80x94to map the subgrahs onto the physical design of the integrated circuit chip.
For routing the channel area a lot of automated prior art methods are known. If such a method is to be employed the subgraphs of the channel areas can be used as input data for such prior art methods.
For routing of the clusters it is advantageous to employ the automated routing method which is described in the dependent method claims. For this method first the actual electrical connectivities which can be established between the nodes in each of the clusters have to be described. This is done by a graph representation which forms the basis of the intra cluster routing method.
According to this method subgraphs which represent the desired electrical interconnections to be established between the nodes in a given cluster are mapped on a graph which represents the potential electrical connectivities within the given cluster. To carry out this procedure no human interaction is required. The steps of the method of the invention can be realized by programming a general purpose digital computer, which is fed with the required design data, i.e. the placement of the clusters, the nets to be wired and the assignment of the nodes of the nets to the clusters.